package main;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Verifier {

	public static boolean isCircle(Pair<Integer, Integer>[] edges, List<Integer> iList) {
		ArrayList<Integer[]> permutations = new ArrayList<Integer[]>();
		 getPermutation(iList, 0, permutations);
		 HashMap<Integer, Integer> vCounter = new HashMap<>();
		 for (Pair<Integer, Integer> e : edges) {
			 Integer l = e.first;
			 Integer r = e.second;
			 
			 if (!vCounter.containsKey(l)){
				 vCounter.put(l, 0);
			 }
			 vCounter.put(l, vCounter.get(l)+1);
			 if (!vCounter.containsKey(r)){
				 vCounter.put(r, 0);
			 }
			 vCounter.put(r, vCounter.get(r)+1);
		} 
			
		for (Integer v : vCounter.keySet()){
			if (vCounter.get(v)!= 2){
				return false;
			}
		}
		 
		for (Integer[] perm : permutations) {
			if (iList.size()==3){
				
				if ( isEdgesConnected(edges[perm[0]], edges[perm[1]]) &&
	         		isEdgesConnected(edges[perm[1]], edges[perm[2]]) &&
	         		isEdgesConnected(edges[perm[2]], edges[perm[0]])) return true;
			}
			if (iList.size()==4){
				
				if ( isEdgesConnected(edges[perm[0]], edges[perm[1]]) &&
	         		isEdgesConnected(edges[perm[1]], edges[perm[2]]) &&
	         		isEdgesConnected(edges[perm[2]], edges[perm[3]]) &&
	         		isEdgesConnected(edges[perm[3]], edges[perm[0]])) {
					
					
					return true;
				}
					
			}
		}
		 return false;
		 
	}
	
	public static boolean isEdgesConnected(Pair<Integer, Integer> edgeA, Pair<Integer, Integer> edgeB){
		if (edgeA.first.equals(edgeB.first) || edgeA.first.equals(edgeB.second)) return true;
		if (edgeA.second.equals(edgeB.first) || edgeA.second.equals(edgeB.second)) return true;
		return false;
	}
	
    static void getPermutation(List<Integer> arr, int k, List<Integer[]> permutations){
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            getPermutation(arr, k+1, permutations);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() -1){
//            System.out.println(java.util.Arrays.toString(arr.toArray()));
            Integer[] perm =arr.toArray(new Integer[0]);
            permutations.add(perm);
           
        }
       
    }
    
    public static boolean verify(int[][] solution){
    	List<Pair<Integer, Integer>> edges = new LinkedList<Pair<Integer, Integer>>();
    	for (int i=0; i<solution.length; i++){
    		for (int j=i+1; j<solution.length; j++){
    			if (solution[i][j]==1)
    				edges.add(new Pair<Integer, Integer>(i, j));
    		}
    	}
    	int numOfPairs = edges.size();//(int)((Math.pow(solution.length, 2) - solution.length)/(double)2);
    	
    	for (int a=0; a<numOfPairs; a++){
			for (int b=a+1; b<numOfPairs; b++){
				for (int c=b+1; c<numOfPairs; c++){
					for (int d=c+1; d<numOfPairs; d++){
						Pair<Integer, Integer>[] pairs = new Pair[]{edges.get(a), edges.get(b), 
																	edges.get(c), edges.get(d)};
						if (Verifier.isCircle(pairs, Arrays.asList(0,1,2,3))){
							return false;
						}
					}
				}
			}
		}
		
		for (int a=0; a<numOfPairs; a++){
			for (int b=a+1; b<numOfPairs; b++){
				for (int c=b+1; c<numOfPairs; c++){
					Pair<Integer, Integer>[] pairs = new Pair[]{edges.get(a), edges.get(b), 
							edges.get(c)};
					if (Verifier.isCircle(pairs, Arrays.asList(0,1,2))){
						return false;
					}
					
				}
			}
		}
    	
    	return true;
    }

    
    public static void main(String[] args) {
    	@SuppressWarnings("unchecked")
		Pair<Integer, Integer>[] edges = new Pair[]{new Pair<Integer, Integer>(1,5),
    			new Pair<Integer, Integer>(1,3),
    			new Pair<Integer, Integer>(2,5),
    			new Pair<Integer, Integer>(2,3)};
    	System.out.println("true = " +isCircle(edges, Arrays.asList(0,1,2,3)));
    	edges[1] = new Pair<Integer, Integer>(7, 5);
    	System.out.println("false = " +isCircle(edges, Arrays.asList(0,1,2,3)));
    	
    	
	}
    
}
